"""
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。

每 3 个士兵可以组成一个作战单位，分组规则如下：

从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中  0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-teams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


# 判断是否为合法队
def check_is_valid(to_check):
    left = to_check[0]
    mid = to_check[1]
    after = to_check[2]
    is_valid = True
    if left < mid:
        if mid < after:
            is_valid = True
        else:
            is_valid = False
    elif mid > after:
        is_valid = True
    else:
        is_valid = False
    return is_valid


def to_count(to_check):
    if check_is_valid(to_check):
        return 1
    else:
        return 0
class Solution:

    def numTeams(self, rating):
        total = 0
        left_rating = []
        # 如果元素个数小于3
        if len(rating) < 3:
            return 0
        for current_idx, current_value in enumerate(rating):
            # 如果是倒数第二个元素了(再循环下去就凑不满三个了)
            if current_idx == len(rating) - 2:
                break
            left_rating = rating[current_idx + 1:]
            bigger = []
            smaller =[]
            for _, value in enumerate(left_rating):
                if value < current_value:
                    smaller.append(value)
                else:
                    bigger.append(value)
            to_check = []
            to_check.append(current_value)
            # 在bigger里
            for bigger_current_idx, bigger_current_value in enumerate(bigger):
                # 如果小于两个直接break
                if len(bigger) < 2:
                    break
                # 找出连续的升序对
                # 加入第一个
                to_check.append(bigger_current_value)
                # 还剩下的，需要再找一个
                bigger_left = bigger[bigger_current_idx + 1:]
                for i in bigger_left:
                    to_check.append(i)
                    total += to_count(to_check)
                    to_check.pop()
                # 删除到只剩第一个
                to_check.pop()
            # 在smaller里
            to_check.clear()
            to_check.append(current_value)
            for smaller_current_idx, smaller_current_value in enumerate(smaller):
                # 如果小于两个直接break
                if len(smaller) < 2:
                    break
                # 找出连续的降序对
                # 加入第一个
                to_check.append(smaller_current_value)
                # 还剩下的，需要再找一个
                smaller_left = smaller[smaller_current_idx + 1:]
                for i in smaller_left:
                    to_check.append(i)
                    total += to_count(to_check)
                    to_check.pop()
                # 删除到只剩第一个
                to_check.pop()
        return total


# print(Solution.numTeams(self=None, rating=[1,2,3,4]))

"""
# 列举中位数
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        ans = 0
        # 枚举三元组中的 j
        for j in range(1, n - 1):
            iless = imore = kless = kmore = 0
            for i in range(j):
                if rating[i] < rating[j]:
                    iless += 1
                # 注意这里不能直接写成 else
                # 因为可能有评分相同的情况
                elif rating[i] > rating[j]:
                    imore += 1
            for k in range(j + 1, n):
                if rating[k] < rating[j]:
                    kless += 1
                elif rating[k] > rating[j]:
                    kmore += 1
            ans += iless * kmore + imore * kless
        return ans

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-number-of-teams/solution/tong-ji-zuo-zhan-dan-wei-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""